package xyf.p10.dp;

/**
 * ClassName: P0494_AimSum
 * Description:
 * Author: xyf
 * Date: 9/9/22 10:24 AM
 * Version: 1.0
 **/
public class P0494_AimSum
{
    public int findTargetSumWays(int[] nums, int target)
    {
        int[][] dp = new int[nums.length][2001];

        dp[0][1000 + nums[0]] += 1;

        dp[0][1000 - nums[0]] += 1;

        for (int i = 1; i < nums.length; i++)
        {
            for (int j = 0; j < 2001; j++)
            {
                if (j - nums[i] > 0)
                {
                    dp[i][j] += dp[i - 1][j - nums[i]];
                }
                if (j + nums[i] < 2001)
                {
                    dp[i][j] += dp[i - 1][j + nums[i]];
                }
            }
        }

        return dp[nums.length - 1][1000 + target];
    }
}